class Solution {
    List<String> ans = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs("", 0, n);
        return ans;
    }

    public void dfs(String s, int stack, int n) {
        if (s.length() == n * 2) {
            if (stack == 0) {
                ans.add(s);
            }
            return;
        }
        if (stack < n) {
            dfs(s + '(', stack + 1, n);
        }
        if (stack > 0) {
            dfs(s + ')', stack - 1, n);
        }
    }
}